package com.mgq.algorithm.twotree;

/**
 * 打印所有折痕
 * 纸条,第一次折, 向下折痕,是凹,向上折痕,是凸
 * 给定n,从纸条的上方向下方依次打印
 *
 *               1凹
 *              /  \
 *            2凹  2凸
 *            / \  / \
 *         3凹 3凸 3凹 3凸
 *
 */
public class PrintAllFold {
    /**
     * 折叠n次,打印所有折痕
     * @param N
     */
    public static void printAllFold(int N) {
        printProcess(1,N,true);
    }

    /**
     * process函数
     * @param i 当前的层数
     * @param N 最大的层数
     * @param down down==true?"凹":"凸"
     */
    public static void printProcess(int i, int N, boolean down) {
        //中序遍历,就是纸条的顺序
        //表示超过的最大次数
        if (i > N) {
            return;
        }
        //打印凹(左子树)
        printProcess(i+1,N,true);
        System.out.println(down==true?"凹":"凸");
        printProcess(i+1,N,false);
    }

    public static void main(String[] args) {
        printAllFold(3);
    }
}
